#include "merge_sort.h"
#include <cstring>

namespace algo
{

void merge_sort(vector<int> &vctNums)
{
    if (vctNums.size() <= 1)
        return ;
    merge_sort_c(vctNums, 0, vctNums.size()-1);
}

void merge_sort_c(vector<int> &vctNums, int p, int r)
{
    if (p >= r) 
        return ;

    int q = (r + p) / 2;      // middle index
    merge_sort_c(vctNums, p, q);
    merge_sort_c(vctNums, q+1, r);

    merge(p, r, vctNums);
}

void merge(int p, int r, vector<int> &vctNums)
{
    int q = (r + p) / 2;  // middle index

    int iReserve = (r - p)/2 +1;        // half size
    vector<int>vctLhs;
    vector<int>vctRhs;
    vctLhs.reserve(iReserve);
    vctRhs.reserve(iReserve);
    merge_copy(vctNums, p, q, vctLhs);
    merge_copy(vctNums, q+1, r, vctRhs);
    int i = 0;
    int j = 0;
    for (i = 0, j = 0; i < vctLhs.size() && j < vctRhs.size(); )
    {
        if (vctLhs[i] <= vctRhs[j])
        {
           vctNums[p++] = vctLhs[i++];
        }
        else
        {
            vctNums[p++] = vctRhs[j++];
        }
    }

    for (; i < vctLhs.size();)
    {
        vctNums[p++] = vctLhs[i++];
    }

    for (; j < vctRhs.size(); )
    {
        vctNums[p++] = vctRhs[j++];
    }
}

void merge_copy(const vector<int> vctFrom, int iBegin, int iEnd, vector<int> &vctTo)
{
    for (int i = iBegin; i <= iEnd; ++i)
    {
        vctTo.push_back(vctFrom[i]);
    }
}

}



